9615. Задача с монетами Фробениуса

 

Имеются монеты двух номиналов x и y. Найдите наибольшую сумму S, которую нельзя выплатить этими двумя номиналами (имеется бесконечное количество монет каждого номинала) и общее количество T сумм, которые нельзя составить имеющимися монетами. Если требуемые значения не существуют, выведите “NA”.

 

Вход. Два натуральных числа x и y (1 < x, y ≤ 109).

 

Выход. Выведите в одной строке два числа: S и T.

 

Пример входа 1

Пример выхода 1

2 5

3 2

 

 

Пример входа 2

Пример выхода 2

5 10

NA

 

 

РЕШЕНИЕ

размен монет

 

Анализ алгоритма

Если НОД(x, y) > 1, то существует бесконечное количество сумм, которые нельзя выплатить двумя номиналами. В этом случае следует вывести “NA”.

Наибольшая сумма S, которую нельзя выплатить номиналами x и y, равна x * y – x – y.

Общее количество T сумм, которые непредставимы имеющимися монетами, равно (x – 1) * (y – 1) / 2.

 

Пример

Рассмотрим пример x = 2, y = 5. В этом случае

S = 2 * 5 – 2 – 5 = 3,

T = 1 * 4 / 2 = 2

Непредставимыми суммами будут 1 и 3 (две суммы).

 

Реализация алгоритма

Функция gcd вычисляет наибольший общий делитель чисел a и b.

 

long long gcd(long long a, long long b)

{

  return (!b) ? a : gcd(b, a % b);

}

 

Основная часть программы. Читаем входные даные.

 

scanf("%lld %lld", &x, &y);

 

Если НОД(x, y) > 1, то существует бесконечное количество сумм, которые нельзя выплатить двумя номиналами.

 

if (gcd(x, y) > 1)

{

  puts("NA");

  return 0;

}

 

s = (x * y) - x - y;

t = (x - 1) * (y - 1) / 2;

printf("%lld %lld\n", s, t);